package puzzle.projecteuler.p200;

import java.math.BigInteger;

import astudy.util.AdvMath;


public class Problem188C {

	/**
	 * phi series:
	 *    2^8 * 5^8 -> 2^10 * 5^7 -> 2^12 * 5^6 -> ... -> 2^22 * 5^1 
	 * -> 2^24 -> ... -> 2^1 -> 2^0 
	 * 
	 * answer	: 95962097
	 * time cost: 47 ms
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		
		BigInteger a = BigInteger.valueOf(1777);
		BigInteger b = BigInteger.valueOf(1855);
		BigInteger m = new BigInteger("100000000");
		
		System.out.println(mod(a, b, m));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	/**
	 * 计算a^^b mod m的结果
	 * 这里只关心gcd(a,m) = 1的情况
	 * @param a
	 * @param b
	 * @param m
	 * @return
	 */
	public static BigInteger mod(BigInteger a, BigInteger b, BigInteger m) {

		BigInteger one = BigInteger.ONE;
		BigInteger d = AdvMath.gcd(a, m);
		if (d.compareTo(one) == 0) {
			if (b.compareTo(one) == 0) {
				return a.mod(m);
			} else if (b.compareTo(one) < 0) {
				throw new RuntimeException("b < 0");
			} else {
				long phi = AdvMath.phi(m.longValue());
				BigInteger pow = mod(a, b.subtract(one), BigInteger.valueOf(phi));
				return a.modPow(pow, m);
			}
		} else {
			throw new RuntimeException("gcd(a,m) > 1");
		}
	}
}
